Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
LinkedIn Medium
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: House Robber II

Problem Statement

You are given an array representing the amount of money each house has. This array models a circle of houses, meaning that the first and last houses are adjacent. You are tasked with figuring out the maximum amount of money you can rob without alerting the neighbors.

The rule is: if you rob one house, you cannot rob its adjacent houses.

Examples

Example 1:

  • Input: [4, 2, 3, 1]
  • Expected Output: 7
  • Justification: Rob the 1st and 3rd house, which gives 4 + 3 = 7.

Example 2:

  • Input: [5, 1, 2, 5]
  • Expected Output: 7
  • Justification: Rob the 1st and 3rd house, which gives 5 + 2 = 7.

Example 3:

  • Input: [1, 2, 3, 4, 5]
  • Expected Output: 8
  • Justification: Rob the 3rd and 5th house, which gives 3 + 5 = 8.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

Solution

The core idea of our algorithm is to split the circular house problem into two simpler linear problems and then solve each linear problem using a dynamic programming approach. Since the first and last houses in the circle are adjacent, we can't rob them both. Thus, we consider two scenarios: robbing houses excluding the first one and robbing houses excluding the last one. For each scenario, we use a helper function that returns the maximum amount we can rob. This helper function utilizes dynamic programming to keep track of the cumulative robbery amounts, ensuring that no two consecutive houses are robbed. Finally, our solution is the maximum of the two scenarios.

  1. Edge Cases Handling: Begin by checking for edge cases:

    • If the input array is null or has a length of 0, return 0 since there are no houses to rob.
    • If there's only one house, return its value.
    • If there are two houses, return the maximum value of the two houses.
  2. Two Scenarios Handling: Due to the circular structure, handle two scenarios:

    • Exclude the first house and compute for the rest.
    • Exclude the last house and compute for the others.

    Use a helper function to compute the maximum for each scenario.

  3. Simple Robber Helper Function: This function calculates the maximum robbing amount for a linear set of houses using dynamic programming:

    • Maintain two variables, prevMax and currMax, to keep track of the max amount robbed up to the previous and current house, respectively.
    • Iterate through each house in the given range (based on the scenario). At each house, decide whether to rob it (in which case you can't rob the previous house) or skip it.
    • For each house, update currMax based on whether robbing the current house results in a larger amount than skipping it.
  4. Return the Maximum: The main function concludes by returning the maximum value from the two scenarios.

Algorithm Walkthrough

Using the input [4, 2, 3, 1]:

  1. Check for edge cases. Since the array has more than two houses, move to the next step.

  2. Calculate the maximum amount that can be robbed for the two scenarios:

    a. For the scenario excluding the last house (consider houses from index 0 to 2):

    • Start with prevMax = 0 and currMax = 0.
    • For the first house (value 4), currMax becomes 4.
    • For the second house (value 2), currMax remains 4 (because 4 > 2 + 0).
    • For the third house (value 3), currMax becomes 7 (because 4 + 3 > 4). So, for this scenario, the maximum is 7.

    b. For the scenario excluding the first house (consider houses from index 1 to 3):

    • Start with prevMax = 0 and currMax = 0.
    • For the second house (value 2), currMax becomes 2.
    • For the third house (value 3), currMax becomes 3 (because 3 > 2).
    • For the fourth house (value 1), currMax remains 3 (because 3 > 1 + 2). So, for this scenario, the maximum is 3.
  3. The main function then returns the maximum of the two scenarios, which is 7 in this case.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity: We are solving the house robber problem twice (once excluding the first house and once excluding the last house). Each run of the house robber problem has a time complexity of (O(n)), where (n) is the number of houses. Thus, our overall time complexity is (O(n)).

Space Complexity: We use a constant amount of space to store our previous and current max values. Hence, the space complexity is (O(1)).

House Robber II (medium)
Coin Change
Mark as Completed

On this page

Problem Statement

Examples

Solution

Algorithm Walkthrough

Code

Complexity Analysis